package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author RuiKnag
 * @create 2021-05-23-19:50
 */
/*
* 我们首先将一个无序的数组调成大顶堆，从非叶子节点开始调整使得他比左右两个节点的值都大即可，然后们输出最头上的节点
*
*
* */
public class HeapTreeSort {
    public static void sort(int arr[]){
        //我们首先将我们的数组调整成为一个有序的数组
        for (int i = arr.length/2; i >=0; i--) {
            adjustHeap(arr,i,arr.length);
        }
        //我们使用把大顶锥的头部元素和第一个元素对换，然后重新进行排序，之后和倒数第二个元素进行交换排序
        for (int i = arr.length-1; i >0 ; i--) {
            Swap.swap(arr,0,i);
            adjustHeap(arr,0,i);
        }
    }


    //输入数组和要调整的位置
    public static void adjustHeap(int[] arr,int i,int length){
        //使用临时变量保存这个值
        int temp = arr[i];

        for (int j=2*i+1;j<length;j=2*j+1){
            if(j+1<length&&arr[j]<arr[j+1]){
                j++;
            }
            if(temp<arr[j]){
                arr[i]=arr[j];
                i=j;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }

    public static void main(String[] args) {
        int[] arr={50,45,40,20,25,35,30,10,15};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
